package link_list;

/**
 * 题目：找出两个链表中第一个公共节点
 * 例：
 * 1 -> 2 -> 4 -> 11 -> 12 -> 13
 *      5 -> 6 ^
 * output -> 11 -> 12 -> 13
 */
public class SameListNode {
    public static void main(String[] args) {
        ListNode common = new ListNode(4);
        common.next = new ListNode(5);
        common.next.next = new ListNode(6);

        SameListNode sameListNode = new SameListNode();
        ListNode node1 = new ListNode(1);
        node1.next = new ListNode(2);
        node1.next.next = new ListNode(3);
        node1.next.next.next = new ListNode(4);
        node1.next.next.next.next = common;

        ListNode node2 = new ListNode(13);
        node2.next = new ListNode(14);
        node2.next.next = new ListNode(15);
        node2.next.next.next = common;

        ListNode listNode = sameListNode.sameNode(node1, node2);
        while (listNode != null) {
            System.out.println(listNode.val);
            listNode = listNode.next;
        }
    }

    /**
     * 差值法
     * 比较两个链表的长度差值，让短的那个先走差值步数。然后一起移动比较就可以得出相同的节点。
     *
     * @param listNode1
     * @param listNode2
     * @return
     */
    public ListNode sameNode(ListNode listNode1, ListNode listNode2) {

        if (listNode1 == null || listNode2 == null) {
            return null;
        }

        int len1 = 0, len2 = 0;
        ListNode c1 = listNode1, c2 = listNode2;

        while (listNode1 != null) {
            len1++;
            listNode1 = listNode1.next;
        }

        while (listNode2 != null) {
            len2++;
            listNode2 = listNode2.next;
        }

        int d = len1 - len2;

        if (d > 0) {
            while (d-- > 0) {
                c1 = c1.next;
            }
        } else if(d < 0) {
            d = -d;
            while (d-- > 0) {
                c2 = c2.next;
            }
        }

        while (c1 != c2) {
            c1 = c1.next;
            c2 = c2.next;
        }

        return c2;
    }

    /**
     * 等值法
     * 设 l1 的长度为 a + c；l2 的长度为 b + c; 则 a + c + b = b + c + a
     *
     * @param listNode1
     * @param listNode2
     * @return
     */
    public ListNode sameNode2(ListNode listNode1, ListNode listNode2) {
        if (listNode1 == null || listNode2 == null) {
            return null;
        }
        ListNode c1 = listNode1, c2 = listNode2;
        while (c1 != c2) {
            c1 = c1 == null ? listNode2 : c1.next;
            c2 = c2 == null ? listNode1 : c2.next;
        }
        return c1;
    }

}
